package problem127_Word_Ladder;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution {
	public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
		int distance=1;
		Queue<String> queue=new LinkedList<>();
		queue.add(beginWord);
		while(!queue.isEmpty()){
			int numPerLevel=queue.size();
			while(numPerLevel-->0){
				String top=queue.poll();
				StringBuilder current=new StringBuilder(top);
				for(int i=0;i<current.length();i++){
					char tmp=current.charAt(i);
					for(char c='a';c<='z';c++){
						current.setCharAt(i, c);
						String newWord=current.toString();
						if(newWord.equals(endWord)){
							return distance+1;
						}
						if(wordList.contains(newWord)){
							queue.add(newWord);
							wordList.remove(newWord);
						}
					}
					current.setCharAt(i, tmp);
				}
			}
			distance++;
		}
		return 0;
    }
	
	public static void main(String[] args){
		Set<String> words=new HashSet<>(Arrays.asList(new String[]{"hot","dot","dog","lot","log"}));
		System.out.println(new Solution().ladderLength("hit", "cog", words));
	}
}
